<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>对多人扫雷课设核心算法的分析 | 蓝湖畔淅淅沥沥的雨</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="序言 一开始打算自己写的，但想起来无敌的xxy早在报告中介绍过这一部分了，便直接拿过来用乐。  项目连接 Wldcmzy&#x2F;Multiplayer-MineSweeper: 网页版多人扫雷 web前端+python flask后端+websocket通讯 JS&#x2F;CSS代码内置于HTML (github.com)  一些定义 复制时序号错乱，不以序号为准。 （7）开荒：用户点击一个未知状态的方格后，">
<meta property="og:type" content="article">
<meta property="og:title" content="对多人扫雷课设核心算法的分析">
<meta property="og:url" content="http://example.com/2022/06/06/%E5%AF%B9%E5%A4%9A%E4%BA%BA%E6%89%AB%E9%9B%B7%E8%AF%BE%E8%AE%BE%E6%A0%B8%E5%BF%83%E7%AE%97%E6%B3%95%E7%9A%84%E5%88%86%E6%9E%90/index.html">
<meta property="og:site_name" content="蓝湖畔淅淅沥沥的雨">
<meta property="og:description" content="序言 一开始打算自己写的，但想起来无敌的xxy早在报告中介绍过这一部分了，便直接拿过来用乐。  项目连接 Wldcmzy&#x2F;Multiplayer-MineSweeper: 网页版多人扫雷 web前端+python flask后端+websocket通讯 JS&#x2F;CSS代码内置于HTML (github.com)  一些定义 复制时序号错乱，不以序号为准。 （7）开荒：用户点击一个未知状态的方格后，">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2022-06-06T13:20:39.000Z">
<meta property="article:modified_time" content="2022-06-06T13:40:19.469Z">
<meta property="article:author" content="StarsWhisper">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="扫雷">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="蓝湖畔淅淅沥沥的雨" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

  
<link rel="stylesheet" href="/plugin/bganimation/bg.css">

  

  <link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css" rel="stylesheet" type="text/css">
<meta name="generator" content="Hexo 6.1.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <div class="outer">
        <div class="widget-wrap mobile-header">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

        <section id="main"><article id="post-对多人扫雷课设核心算法的分析" class="wow slideInRight article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2022/06/06/%E5%AF%B9%E5%A4%9A%E4%BA%BA%E6%89%AB%E9%9B%B7%E8%AF%BE%E8%AE%BE%E6%A0%B8%E5%BF%83%E7%AE%97%E6%B3%95%E7%9A%84%E5%88%86%E6%9E%90/" class="article-date">
  <time class="post-time" datetime="2022-06-06T13:20:39.000Z" itemprop="datePublished">
    <span class="post-month">6月</span><br/>
    <span class="post-day">06</span>
  </time>
</a>
   
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      对多人扫雷课设核心算法的分析
    </h1>
  

        <div>
          
  <div class="article-category">
    <a class="article-category-link" href="/categories/%E8%AF%BE%E7%A8%8B%E8%AE%BE%E8%AE%A1/">课程设计</a>,<a class="article-category-link" href="/categories/%E8%AF%BE%E7%A8%8B%E8%AE%BE%E8%AE%A1/%E7%BD%91%E9%A1%B5%E7%89%88%E5%A4%9A%E4%BA%BA%E6%89%AB%E9%9B%B7/">网页版多人扫雷</a>
  </div>

          
              

          
        </div>
      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="序言"><a class="markdownIt-Anchor" href="#序言"></a> 序言</h1>
<p>一开始打算自己写的，但想起来无敌的xxy早在报告中介绍过这一部分了，便直接拿过来用乐。</p>
<h1 id="项目连接"><a class="markdownIt-Anchor" href="#项目连接"></a> 项目连接</h1>
<p><a target="_blank" rel="noopener" href="https://github.com/Wldcmzy/Multiplayer-MineSweeper">Wldcmzy/Multiplayer-MineSweeper: 网页版多人扫雷 web前端+python flask后端+websocket通讯 JS/CSS代码内置于HTML (github.com)</a></p>
<h1 id="一些定义"><a class="markdownIt-Anchor" href="#一些定义"></a> 一些定义</h1>
<p><strong>复制时序号错乱，不以序号为准。</strong></p>
<p>（7）开荒：用户点击一个未知状态的方格后，根据开荒规则打开一片区域。开荒有2个阶段：点击开荒、遍历开荒，分别对应两种开荒规则，规则请参照定义第8、9条。</p>
<p>（8）点击开荒规则：点击开荒阶段的规则。先打开用户点击位置的方格。如果用户点击位置方格打开状态不是雷，则打开八方位方格中打开状态为0的方格。</p>
<p>（9）遍历开荒规则：遍历开荒阶段的规则。对打开的八方位方格中的方格继续进行开荒。如果方格打开状态是0，打开八方位的全部方格，然后重复执行该遍历开荒规则；如果方格打开状态是1、2、3、4、5、6、7、8，停止当前方格的遍历开荒。</p>
<p>（1） 时间戳：用户点击请求到达服务器的相对时间顺序。</p>
<p>（2） 用户颜色：每个用户在每一局游戏中会获得一个颜色，雷区地图上用用户颜色标识用户开荒区域。同一用户在同一局游戏中始终具有相同的用户颜色，用户的退出不能更改本局的用户颜色。游戏重开后，用户颜色重置。</p>
<p>（3） 染色：将用户开荒区域的方格由初始颜色变更为用户颜色。</p>
<p>（4） 染色修正：用户颜色的修正。在多人进行游戏时，因为数据传输的延迟，所以前端收到的广播顺序不一定是操作到达服务器的顺序。所以有可能出现用户A的点击请求先到达服务端，由于服务端还未广播A的点击或者前端收到了广播还没有进行开荒，用户B可能点击了和用户A开荒的区域有交集的位置，用户B的点击请求也会到达服务端。服务器会先广播A的点击，后广播B的点击。用户B的广播可能先到前端，这样前端就会将区域判定为用户B的区域导致错误。所以增加染色修正的概念。前端会根据染色修正规则将开荒区域调整为正确的颜色。染色修正规则请参照定义第18条。</p>
<p>（5） 染色修正规则：以时间戳为依据，方格的颜色为时间戳最小的用户对应的用户颜色。</p>
<h1 id="算法分析"><a class="markdownIt-Anchor" href="#算法分析"></a> 算法分析</h1>
<h2 id="1-雷区生成算法"><a class="markdownIt-Anchor" href="#1-雷区生成算法"></a> 1、雷区生成算法</h2>
<p>雷区生成算法的参数有：子区域行列数、子区域雷数、雷区地图行数、雷区地图列数、模数、雷区种子、斐波那契数列值。</p>
<p>设置子区域的目的是为了防止部分区域雷的密度不够，一次开荒出大片区域，递归栈空间不够用。同时也是为了更好的用户体验。将雷区地图按照子区域行列数进行划分，依次进行每个子区域的地图生成。划分边界的不够完整的子区域的雷区，按照完整子区域的雷的密度计算得出该区域的雷数。</p>
<p>斐波那契数列值用于辅助进行子区域布雷，每局雷区地图生成初始为数列第1项。</p>
<p>子区域地图生成：</p>
<p>（1）子区域按顺序从上到下、从左到右对每个方格依次进行编号，编号从0开始，每次递增1。最终编号小于子区域雷数的方格为有雷的方格。</p>
<p>（2）定义辅助变量delta，初始化令其等于雷区种子</p>
<p>（3）子区域按顺序从上到下、从左到右枚举，对枚举到的每个格子进行编号的交换。交换规则：先递推一次斐波那契数列，辅助变量delta和斐波那契数列值相乘，并对模数取模。若取模结果大于子区域雷数，持续和斐波那契数列值相乘，直至取模结果小于子区域雷数。delta%行数为交换位置的子区域行号。再将delta除以子区域行数，delta%列数为交换位置的子区域列号。交换枚举位置和交换位置的两个方格的数字。</p>
<p>（4）将子区域地图信息转移到雷区地图上。</p>
<h2 id="2-开荒算法"><a class="markdownIt-Anchor" href="#2-开荒算法"></a> 2、开荒算法</h2>
<p>根据定义中的点击开荒规则和遍历开荒规则进行dfs遍历雷区地图。具体有四种情况：</p>
<p>（1）前端同步本局历史数据时：由于接收到的历史数据是按按照时间戳排好序的，所以直接按照规则进行dfs遍历，同时在遍历过程中进行染色。</p>
<p>（2）前端收到广播时：由于收到的广播顺序不一定是按时间戳排好序的，所以按照规则进行dfs遍历，同时在遍历过程中进行染色，如果在dfs遍历中发生要对已染色的区域再次染色，则参考染色修正规则。</p>
<p>（3）前端进行用户本地开荒时：只按照规则进行dfs遍历，不染色。</p>
<p>（4）后端遍历：因为时间戳表示到达后端的时间，所以后端直接判断初始位置是否被遍历过，若没有，进行遍历即可。</p>
<h2 id="3-用户颜色分配算法"><a class="markdownIt-Anchor" href="#3-用户颜色分配算法"></a> 3、用户颜色分配算法</h2>
<p>颜色库中规定多种色调的颜色，每种色调有若干亮度不同的颜色。</p>
<p>（1）确定色调：随机一个颜色范围不大于色调的随机数，若该色调使用次数为色调最少使用次数，则确定为该色调，否则向后循环遍历色调，直到找到使用次数为色调最少使用次数的色调。</p>
<p>（2）确定颜色：随机一个不大于该色调颜色数的随机数，若该颜色使用次数为色调内颜色最少使用次数，则确定为该颜色，否则向后循环遍历色调内的颜色，直到找到使用次数为色调内颜色最少使用次数的色调。</p>
<h2 id="4-染色修正规则"><a class="markdownIt-Anchor" href="#4-染色修正规则"></a> 4、染色修正规则</h2>
<p>在染色的时候，永远遵循染时间戳更小的用户颜色。即在发生要对已染色的区域再次染色时：</p>
<p>（1）如果原方格的时间戳更小，则颜色不更改。</p>
<p>（2）如果新的时间戳更小，则更改方格的颜色和时间戳。</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/2022/06/06/%E5%AF%B9%E5%A4%9A%E4%BA%BA%E6%89%AB%E9%9B%B7%E8%AF%BE%E8%AE%BE%E6%A0%B8%E5%BF%83%E7%AE%97%E6%B3%95%E7%9A%84%E5%88%86%E6%9E%90/" data-id="cl42s4wxo0000bwj3g9mufu22" class="article-share-link">分享</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E6%89%AB%E9%9B%B7/" rel="tag">扫雷</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2022/06/09/Git%E4%BD%BF%E7%94%A8%E6%80%BB%E7%BB%93-%E4%BB%85%E9%83%A8%E5%88%86%E5%8A%9F%E8%83%BD/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">上一篇</strong>
      <div class="article-nav-title">
        
          Git使用总结(仅部分功能)
        
      </div>
    </a>
  
  
    <a href="/2022/06/06/linux%E6%9C%8D%E5%8A%A1%E5%99%A8%E4%B8%8A%E9%80%9A%E8%BF%87python%E8%84%9A%E6%9C%AC%E8%87%AA%E5%8A%A8%E6%8E%A7%E5%88%B6mysql%E6%95%B0%E6%8D%AE%E5%BA%93/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">下一篇</strong>
      <div class="article-nav-title">python语言实现服务器对mysql数据库的自动处理</div>
    </a>
  
</nav>

  
</article>



</section>
        
          <aside id="sidebar">
  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <h1 class="blog-title">蓝湖畔淅淅沥沥的雨</h1>
    <h2 class="blog-subtitle">All tragedy erased, I see only wonders...</h2>
    <ul class="blog-link">
     
          <a href="/" title="Home">
            <li>主页</li>
          </a>
        
          <a href="/archives" title="Archives">
            <li>归档</li>
          </a>
        
          <a href="/categories" title="Categories">
            <li>分类</li>
          </a>
        
          <a href="/tags" title="Tags">
            <li>标签</li>
          </a>
        
          <a href="/knightabout" title="Knightabout">
            <li>关于</li>
          </a>
        
          <a href="/bridges" title="Bridges">
            <li>传送门</li>
          </a>
        
          <a href="/announcement" title="Announcement">
            <li>公告</li>
          </a>
        
    </ul>
  </div>
</div>

  
    <div class="widget-wrap">
  <h3 class="widget-title"></h3>
  <div class="widget">
    <img class="avatar" src="/images/avatar.png">
    <h2 class="author">StarsWhisper</h2>
    <h3 class="description"></h3>
    <div class="count-box">
      <a href="/archives"><div><strong>75</strong><br>文章</div></a>
      <a href="/categories"><div><strong>31</strong><br>分类</div></a>
      <a href="/tags"><div><strong>56</strong><br>标签</div></a>
    </div>



    <div class="social-link">
      
        <a class="hvr-bounce-in" href="https://github.com/Wldcmzy" target="_blank" title="Github">
          Github
        </a>
      
        <a class="hvr-bounce-in" href="https://blog.csdn.net/wldcmzy" target="_blank" title="CSDN">
          CSDN
        </a>
      
        <a class="hvr-bounce-in" href="https://space.bilibili.com/83743701" target="_blank" title="bilibili(无技术和学习内容)">
          bilibili(无技术和学习内容)
        </a>
      
    </div>

    <div class="friend-link">
      <h2>友情链接</h2>
      
        <a class="hvr-bounce-in" href="https://shanamaid.github.io/" target="_blank" title="夏娜主题作者的博客">
          夏娜主题作者的博客
        </a>
      
    </div>
  </div>
</div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy;2021 - 2022 StarsWhisper<br>
      由<a href="http://hexo.io/" target="_blank">Hexo</a>强力驱动 | 
      主题-<a target="_blank" rel="noopener" href="https://github.com/ShanaMaid/hexo-theme-shana">Shana</a>(但是魔改)
      
    </div>
    
  </div>
</footer>
    </div>
    

<script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>
<script src="//apps.bdimg.com/libs/wow/0.1.6/wow.min.js"></script>
<script>
new WOW().init();
</script>   


  
<link rel="stylesheet" href="/plugin/fancybox/jquery.fancybox.css">

  
<script src="/plugin/fancybox/jquery.fancybox.pack.js"></script>




  
<link rel="stylesheet" href="/plugin/galmenu/GalMenu.css">

  
<script src="/plugin/galmenu/GalMenu.js"></script>

  <div class="GalMenu GalDropDown">
      <div class="circle" id="gal">
        <div class="ring">
          
            <a href="/announcement" title="" class="menuItem">公告</a>
          
            <a href="/tags" title="" class="menuItem">标签</a>
          
            <a href="/categories" title="" class="menuItem">分类</a>
          
            <a href="/archives" title="" class="menuItem">归档</a>
          
            <a href="/knightabout" title="" class="menuItem">关于</a>
          
            <a href="/bridges" title="" class="menuItem">传送门</a>
          
        </div>
        
          <audio id="audio" src="#"></audio>
        
      </div> 
</div>
<div id="overlay" style="opacity: 1; cursor: pointer;"></div>
  <script type="text/javascript">var items = document.querySelectorAll('.menuItem');
    for (var i = 0,
    l = items.length; i < l; i++) {
      items[i].style.left = (50 - 35 * Math.cos( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%";
      items[i].style.top = (50 + 35 * Math.sin( - 0.5 * Math.PI - 2 * (1 / l) * i * Math.PI)).toFixed(4) + "%"
    }</script>
<script type="text/javascript">
  $(document).ready(function() {
    $('body').GalMenu({
      'menu': 'GalDropDown'
    })
  });
</script>

  <section class="hidden-xs"> 
  <ul class="cb-slideshow"> 
    <li><span>苟利</span></li> 
    <li><span>国家</span></li> 
    <li><span>生死以</span></li> 
    <li><span>岂能</span></li> 
    <li><span>祸福</span></li> 
    <li><span>趋避之</span></li> 
  </ul>
</section>

<script src="/js/script.js"></script>




  </div>
</body>
</html>